package leetcode.code1238;

import java.util.ArrayList;
import java.util.List;

public class Solution {


	List<Integer> ans;
	int n;

	public List<Integer> circularPermutation(int n, int start) {
		ans = new ArrayList<>();
		this.n = n;
		boolean[] used = new boolean[1 << n];
		this.f(start, used, 1);
		return ans;
	}

	private boolean f(int start, boolean[] used, int idx) {
		ans.add(start);
		if (idx == 1 << n) {
			return true;
		}
		used[start] = true;
		for (int i = 0; i < n; i++) {
			int num = start ^ (1 << i);
			if (!used[num] && this.f(num, used, idx + 1)) {
				return true;
			}
		}
		used[start] = false;
		ans.add(ans.size() - 1);
		return false;
	}

}
